{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题目描述\n",
    "[P3. Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)\n",
    "\n",
    "Given a string, find the length of the longest substring without repeating characters.\n",
    "\n",
    "Example 1:\n",
    "Input: \"abcabcbb\"\n",
    "\n",
    "\n",
    "Output: 3 \n",
    "Explanation: The answer is \"abc\", with the length of 3. \n",
    "\n",
    "\n",
    "Example 2:\n",
    "Input: \"bbbbb\"\n",
    "\n",
    "\n",
    "Output: 1\n",
    "Explanation: The answer is \"b\", with the length of 1.\n",
    "\n",
    "\n",
    "Example 3:\n",
    "Input: \"pwwkew\"\n",
    "\n",
    "\n",
    "Output: 3\n",
    "Explanation: The answer is \"wke\", with the length of 3. \n",
    "             \n",
    "\n",
    "Note that the answer must be a substring, \"pwke\" is a subsequence and not a substring.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 解题思路\n",
    "\n",
    ">下面使用的差不多就是暴搜，速递比较慢...\n",
    ">\n",
    ">函数`check_n`就是看下最长子串是不是`n`,之后遍历所有可能的`n`，其中通过set算出最大的`n`，减少遍历次数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-01-20T14:25:41.169889Z",
     "start_time": "2019-01-20T14:25:41.161463Z"
    }
   },
   "source": [
    "### Python代码[42.57%]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-01-20T14:25:59.258535Z",
     "start_time": "2019-01-20T14:25:59.238184Z"
    }
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # \"\"处理\n",
    "        if s == \"\":\n",
    "            return 0\n",
    "        # is n?\n",
    "        def check_n(s, n):\n",
    "            if n == 1:\n",
    "                return True\n",
    "            for i in range(0, len(s)-n+1):\n",
    "                if len(set(s[i:i+n])) == n:\n",
    "                    return True\n",
    "            return False\n",
    "                \n",
    "        # 缩短搜索范围,长度上界\n",
    "        N = len(set(s))\n",
    "        # 遍历搜索\n",
    "        for i in range(1, N+1):\n",
    "            if check_n(s, i):\n",
    "                length = i\n",
    "                continue\n",
    "            else:\n",
    "                break\n",
    "        return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-01-20T14:26:29.049569Z",
     "start_time": "2019-01-20T14:26:29.021657Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 测试\n",
    "s = Solution()\n",
    "s.lengthOfLongestSubstring(\"pwwkew\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 优秀代码学习\n",
    "\n",
    ">应该是滑动窗口，还没彻底搞清楚..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        usedChar={}\n",
    "        start=maxLength=0\n",
    "        for index,char in enumerate(s):\n",
    "            if char in usedChar and start<=usedChar[char]:\n",
    "                start=usedChar[char]+1\n",
    "            else:\n",
    "                maxLength=max(maxLength,index-start+1)\n",
    "            usedChar[char]=index\n",
    "        return maxLength"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.6"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
